package com.jxb.test20241216;

import java.util.ArrayList;

public class Sort7 {

    public static void main(String[] args) {
        int count  = 100;
        int bucketCount = 0;
        while (count > 1) {
            count = count / 10;
            bucketCount++;
        }
        System.out.println(bucketCount);
    }

    public static int[] sortArray(int[] nums) {
        if (nums == null) {
            return null;
        }
        //计算需要多少桶，获取最大值，计算出最大值的位数，位数即为桶位
        int count = 0;
        for (int i = 0;i<nums.length;i++) {
            if(i == 0) {
                count = nums[i];
            }else {
                if (count < nums[i]) {
                    count = nums[i];
                }
            }
        }
        int bucketCount = 0;
        while (count > 1) {
            count = count / 10;
            bucketCount++;
        }

        //构造桶
        ArrayList<ArrayList<Integer>> indBuckets = new ArrayList<>();
        for (int i = 0;i<bucketCount;i++) {
            indBuckets.add(new ArrayList<>());
        }

        //遍历，将每一位数进行入桶
        int mode = 10;
        int div = 1;
        for (int i = 0;i<bucketCount;i++,mode*=100,div*=100) {
            for (int j = 0;j<nums.length;j++) {
                //计算元素对应位置的数值
                int index = (nums[j]%mode)/div;
                indBuckets.get(index).add(nums[index]);
            }
            //对当前的元素的位数进行排序
            int index = 0;
            for (int j = 0;j<indBuckets.size();j++) {
                ArrayList<Integer> elements = indBuckets.get(j);
                //排序
                sortElements(elements);
                //更新原数组
                for (Integer el : elements) {
                    nums[index++] = el;
                }
                indBuckets.get(j).clear();
            }
        }
        return nums;
    }


    private static void sortElements(ArrayList<Integer> elements) {
        if (elements != null) {
            int currentValue;
            for (int i = 0;i<elements.size();i++) {
                int preIndex = i;
                currentValue = elements.get(i+1);
                while (preIndex > 0 && currentValue < elements.get(i)) {
                    elements.set(preIndex + 1,elements.get(preIndex));
                    preIndex -- ;
                }
                elements.set(preIndex+1,currentValue);
            }
        }
    }

}
